class Solution:
    def minPatches(self, nums: list, n: int) -> int:
        """有很大的测试用例,内存会超"""
        he_set = set()
        for num in nums:
            mid_set = {num, }
            for he in he_set:
                mid_set.add(num + he)
            he_set.update(mid_set)
        # print(he_set)
        res = 0
        for i in range(1, n + 1):
            if i not in he_set:
                res += 1
                mid_set = {i, }
                for he in he_set:
                    mid_set.add(i + he)
                he_set.update(mid_set)
        return res


import math


class Solution:
    def minPatches(self, nums: list, n: int) -> int:
        if not nums:
            return math.floor(math.log(n, 2)) + 1
        if not n:
            return 0
        if nums[0] == 1:
            mid_max, res, i = 1, 0, 1
        else:
            mid_max, res, i = 1, 1, 0
        length = len(nums)
        while mid_max < n:
            max_add = mid_max + 1
            if i < length and nums[i] <= max_add:
                mid_max += nums[i]
                i += 1
            else:
                res += 1
                mid_max += max_add
        return res


class Solution:
    def minPatches(self, nums: list, n: int) -> int:
        """这个还有点小问题"""
        if not nums:
            return math.floor(math.log(n, 2)) + 1
        if not n:
            return 0
        if nums[0] == 1:
            mid_max, res, i = 1, 0, 1
        else:
            mid_max, res, i = 1, 1, 0
        length = len(nums)
        while mid_max < n:
            max_add = mid_max + 1
            if nums[i] <= max_add:
                mid_max += nums[i]
                i += 1
                if i >= length:
                    break
            else:
                res += 1
                mid_max += max_add
        if mid_max < n:
            res += math.floor(math.log(n / mid_max, 2)) + 1
        return res


a = Solution()
print(a.minPatches(nums=[1, 3], n=6))
print(a.minPatches(nums=[1, 5, 10], n=20))
print(a.minPatches(nums=[1, 2, 2], n=5))
print(a.minPatches(nums=[], n=8))
print(a.minPatches(nums=[1, 2, 4, 8, 14, 28], n=8))
print(a.minPatches([1, 2, 31, 33], 2147483647))  # 28
print(a.minPatches([1, 2, 32], 2147483647))  # 28
